package binarytree

func lowestCommonAncestor235(root, p, q *TreeNode) *TreeNode {
	if root == nil || p == nil || q == nil {
		return nil
	}

	if root == p {
		return p
	}

	if root == q {
		return q
	}

	if p.Val < root.Val && q.Val < root.Val {
		return lowestCommonAncestor235(root.Left, p, q)
	}

	if p.Val > root.Val && q.Val > root.Val {
		return lowestCommonAncestor235(root.Right, p, q)
	}

	return root

}
